package datastructure.graph.最短路径;

import datastructure.graph.有向图.TopologicalSort;

import java.util.Stack;

/**
 * @author MaoLin Wang
 * @description
 * @date 2020/8/28 3:40 下午
 */
public class AcyclicLP {
    private DirectedEdge[] edgeTo;
    private double[] distTo;

    public AcyclicLP(EdgeWeightedDigraph digraph,int s) {
        edgeTo=new DirectedEdge[digraph.V()];
        distTo=new double[digraph.V()];

        for (int i = 0; i < digraph.V(); i++) {
            distTo[i]=Double.MAX_VALUE;
        }
        distTo[s]=0.0;
        TopologicalSort sort=new TopologicalSort(digraph);
        if (!sort.hasOrder()){
            throw new RuntimeException("没有拓扑序列");
        }
        for (Integer v : sort.order()) {
            relax(digraph,v);
        }
    }

    private void relax(EdgeWeightedDigraph digraph, Integer v) {
        for (DirectedEdge edge : digraph.adj(v)) {
            if (distTo[edge.to()]>distTo[v]+edge.weight()){
                distTo[edge.to()]=distTo[v]+edge.weight();
                edgeTo[edge.to()]=edge;
            }
        }
    }
    public double distTo(int v){
        return distTo(v);
    }
    public boolean hasPathTo(int v){
        return distTo(v)<Double.POSITIVE_INFINITY;
    }

    public Iterable<DirectedEdge> pathTo(int v){
        Stack<DirectedEdge> path=new Stack<>();
        for ( DirectedEdge edge=edgeTo[v]; edge!=null ; edge=edgeTo[edge.from()]) {
            path.push(edge);
        }
        return path;
    }

    public static void main(String[] args) {

        EdgeWeightedDigraph graph=new EdgeWeightedDigraph(8);
        graph.addEdge(new DirectedEdge(4,5,0.35));
        graph.addEdge(new DirectedEdge(4,7,0.37));
        graph.addEdge(new DirectedEdge(5,7,0.28));
        graph.addEdge(new DirectedEdge(0,7,0.16));
        graph.addEdge(new DirectedEdge(1,5,0.32));
        graph.addEdge(new DirectedEdge(0,4,0.38));
        graph.addEdge(new DirectedEdge(2,3,0.17));
        graph.addEdge(new DirectedEdge(1,7,0.19));
        graph.addEdge(new DirectedEdge(0,2,0.26));
        graph.addEdge(new DirectedEdge(1,2,0.36));
        graph.addEdge(new DirectedEdge(1,3,0.29));
        graph.addEdge(new DirectedEdge(2,7,0.34));
        graph.addEdge(new DirectedEdge(6,2,0.40));
        graph.addEdge(new DirectedEdge(3,6,0.52));
        graph.addEdge(new DirectedEdge(6,0,0.58));
        graph.addEdge(new DirectedEdge(6,4,0.93));
        AcyclicLP lp=new AcyclicLP(graph,0);
        System.out.println(lp.pathTo(5));
    }
}
